/**
 * 给出n数对。在每一个数对中，第一个数字总是比第二个数字小。
 *
 * 现在，我们定义一种跟随关系，当且仅当b < c时，数对(c, d)才可以跟在(a, b)后面。我们用这种形式来构造一个数对链。
 *
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *
 *
 *思路：贪心
 */
class FindLongestChainTanXin {
    public int findLongestChain(int[][] pairs) {
        if(pairs==null) {
            return 0;
        }
        PriorityQueue<int[]> qu=new PriorityQueue<>(((o1, o2) -> o1[1]-o2[1]));
        int len=pairs.length;
        for(int i=0;i<len;i++) {
            qu.offer(pairs[i]);
        }
        int count=1;
        int cur=qu.poll()[1];
        while(!qu.isEmpty()) {
            if(cur<qu.peek()[0]) {
                count++;
                cur=qu.poll()[1];
            }else {
                qu.poll();
            }

        }
        return count;
}
}